The present disclosure relates to an image processing apparatus that segments an image into plural regions by using a discrete optimization method, such as graph cuts and QPBO (Quadratic Pseudo-Boolean Optimization), an image processing program and an operation method of the image processing apparatus.
Energy minimization using an algorithm for minimum cut of a graph (graph cuts) became widely applied to image processing in recent years. In particular, a method for efficiently solving an image segmentation (region segmentation) problem, as an energy minimization problem, has been proposed.
Graph cuts developed basically with respect to second order energy, which depends on two variables. Meanwhile, V. Kolmogorov and R. Zabih, proposed a method for minimizing submodular third order energy, which depends on three variables (for example, V. Kolmogorov and R. Zabih, “What Energy Functions Can Be Minimized via Graph Cuts?”, IEEE TRANSACTIONS ON PAMI, Vol. 26, No. 2, pp. 147-159, 2004 (Non-Patent Document 1)).
Further, a method for solving a high order energy function of fourth order or higher by transforming the high order energy function to a second order energy function has been proposed. When all of coefficients of quadratic terms of the energy function after transformation are negative, the function is referred to as a submodular function, and a minimum solution is obtainable at high speed by using Max-Flow/Min-Cut algorithm. Meanwhile, when a positive value is included in coefficients of quadratic terms of the energy function after transformation (non-submodular), optimization of the original high order energy function is possible by minimization or obtainment of an approximate solution by using QPBO algorithm. As this energy function transformation, plural methods are known. For example, Rother et al. proposed this transformation (for example, C. Rother et al., “Minimizing Sparse Higher Order Energy Functions of Discrete Variables”, IEEE, CVPR, pp. 1382-1389, 2009 (Non-Patent Document 2)).
Further, a method has been proposed in which a graph cut technique is used to extract a region of a target to be extracted. In the method, energy is set based on a distance from a closed curve representing an outline of the target, and segmentation into an object region and the other region is performed (for example, Japanese Unexamined Patent Publication No. 2012-027713 (Patent Document 1)).